/**************************************************************************
*   Copyright (C) 2009 Chernov Dmitry                                     *
*   diman4ik.chernov@gmail.com                                            *
*                                                                         *
*   This program is free software; you can redistribute it and/or modify  *
*   it under the terms of the GNU General Public License as published by  *
*   the Free Software Foundation; either version 2 of the License, or     *
*   (at your option) any later version.                                   *
*                                                                         *
*   This program is distributed in the hope that it will be useful,       *
*   but WITHOUT ANY WARRANTY; without even the implied warranty of        *
*   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the         *
*   GNU General Public License for more details.                          *
*                                                                         *
*   You should have received a copy of the GNU General Public License     *
*   along with this program; if not, write to the                         *
*   Free Software Foundation, Inc.,                                       *
*   59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.             *
***************************************************************************/

#include "korners_game_engine.h"

#include <QPoint>
#include <KDebug>
#include <QMetaType>

#include <list>


KornersEngine::KornersEngine( QObject* parent ) : QObject(parent)
{
    qRegisterMetaType<KornersMove>("KornersMove");
    memset(m_field, empty, FIELD_SIZE*FIELD_SIZE);
    for(int i = 0; i < N_CAPS; i++)
    {
        if(i < N_CAPS/2)
            m_field[i%IN_ROW + (i/IN_ROW)*FIELD_SIZE] = opponent;
        else
            m_field[i%IN_ROW + IN_ROW + ( (i - IN_ROW*N_ROWS)/IN_ROW + FIELD_SIZE - N_ROWS )*FIELD_SIZE] = player;
    }
}

static bool isNeighbour( QPoint pnt1, QPoint pnt2 )
{
    return  ( ( ( pnt1.x() == pnt2.x() + 1 ) || ( pnt1.x() == pnt2.x() - 1 ) ) && ( pnt1.y() == pnt2.y() ) ) ||
            ( ( ( pnt1.y() == pnt2.y() + 1 ) || ( pnt1.y() == pnt2.y() - 1 ) ) && ( pnt1.x() == pnt2.x() ) );
}

bool KornersEngine::makePath(QPoint src, QPoint dst, KornersMove& mv)
{
    if( isNeighbour( src, dst ) )
    {
        mv.points.push_back(src);
        mv.points.push_back(dst);
        return true;
    }

    bool reachable_src[ FIELD_SIZE*FIELD_SIZE ];
    memset( reachable_src, false, FIELD_SIZE*FIELD_SIZE );
    bool reachable_dst[ FIELD_SIZE*FIELD_SIZE ];
    memset( reachable_dst, false, FIELD_SIZE*FIELD_SIZE );
    
    markReachable( src, none, reachable_src);
    markReachable( src, none, reachable_dst);

    // Points that are reachable both from source and destination
    for( int i = 0; i < FIELD_SIZE*FIELD_SIZE; i++ )
        reachable_src[i] = reachable_src[i] & reachable_dst[i];
    
    std::list<KornersMove> paths_src;
    std::list<KornersMove> paths_dst;
    std::list<QPoint> points;

    bool reachable = false; 

    for( int i = 0; i < FIELD_SIZE*FIELD_SIZE; i++ )
    {
        if( reachable_src[i] )
        {
            QPoint nxt = indexToPoint(i);
            if( nxt == dst)
                reachable = true;
            points.push_back( nxt );
        }
    }

    if( !reachable )
            return false;

    KornersMove from_src;
    KornersMove from_dst;

    from_src.points.push_back(src);
    from_dst.points.push_back(dst);

    paths_src.push_back(from_src);
    paths_dst.push_back(from_dst);

    std::list<KornersMove>::iterator it_paths_src;
    std::list<KornersMove>::iterator it_paths_dst;
    std::list<QPoint>::iterator it_points;

    bool connected = false;
    QPoint where_connected;

    std::list<KornersMove>::iterator tail;

    for( int i =  0; i < 5; i++ )
    {
        for( it_points = points.begin(); it_points != points.end(); ++it_points )
        {
            for( it_paths_src = paths_src.begin(); it_paths_src != paths_src.end(); ++it_paths_src )
            {
                if( ( isNeighbour( it_paths_src->points.last(), *it_points ) ) &&
                    !it_paths_src->points.contains( *it_points ) )
                {
                    if(! ( ( m_field[ pointToIndex( it_paths_src->points.last() ) ] == empty ) &&
                           ( m_field[ pointToIndex( *it_points ) ] == empty ) ) )
                    {
                        KornersMove new_path( *it_paths_src );
                        new_path.points.push_back( *it_points );
                        paths_src.push_back(new_path);
                        connected = true;

                        if( *it_points == dst )
                            goto m;
                    }
                }
            }

            for( it_paths_dst = paths_dst.begin(); it_paths_dst != paths_dst.end(); ++it_paths_dst )
            {
                if( ( isNeighbour( it_paths_dst->points.last(), *it_points ) ) &&
                    !it_paths_dst->points.contains( *it_points ) )
                {
                    if(! ( ( m_field[ pointToIndex( it_paths_dst->points.last() ) ] == empty ) &&
                           ( m_field[ pointToIndex( *it_points ) ] == empty ) ) )
                    {
                        KornersMove new_path( *it_paths_dst );
                        new_path.points.push_back( *it_points );
                        paths_dst.push_back(new_path);
                        if( connected )
                        {
                            tail = it_paths_dst;
                            where_connected = *it_points;
                            goto m;
                        }

                        if( *it_points == src )
                            goto m;
                    }
                }
            }
            connected = false;
        }
    }

    return false;
                
m:
    if( connected )
    {
        for( it_paths_src = paths_src.begin(); it_paths_src != paths_src.end(); ++it_paths_src )
        {
            if( ( it_paths_src->points.first() ==  src ) && ( it_paths_src->points.last() ==  dst ) )
            {
                for( int i = 0; i < it_paths_src->points.size(); i++ )
                    mv.points.push_back( it_paths_src->points[i] );
                return true;
            }
            else if( ( it_paths_src->points.first() ==  src ) && ( it_paths_src->points.last() ==  where_connected ) )
            {
                for( int i = 0; i < it_paths_src->points.size(); i++ )
                    mv.points.push_back( it_paths_src->points[i] );
                for( int i = tail->points.size() - 1; i >= 0; i-- )
                    mv.points.push_back( tail->points[i] );
                return true;
            }               
        }       
    }

    for( it_paths_dst = paths_dst.end(); it_paths_dst != paths_dst.end(); ++it_paths_dst )
    {
        if( ( it_paths_dst->points.first() ==  dst ) && ( it_paths_dst->points.last() ==  src ) )
        {
            for( int i = it_paths_dst->points.size() - 1; i >= 0; i-- )
                mv.points.push_back( it_paths_dst->points[i] );
            return true;
        }
    }

    return false;
}

bool KornersEngine::tryJump( QPoint& src, direction dir, bool* saveThere ) const
{
    switch(dir)
    {
        case north:
            if( src.y() - 1 < 0 )
                return false;
            if( m_field[src.x() + (src.y() - 1)* FIELD_SIZE] != empty )
                return false;
            else
            {
		saveThere[ pointToIndex(src) ] = true;
                src.ry() -= 1;
            }
            break;
        case east:
            if( src.x() + 1 >= FIELD_SIZE )
                return false;
            if( m_field[src.x() + 1 + src.y()* FIELD_SIZE] != empty )
                return false;
            else
            {
		saveThere[ pointToIndex(src) ] = true;
                src.rx() += 1;
            }
            break;
        case south:
            if( src.y() + 1 >= FIELD_SIZE )
                return false;
            if( m_field[src.x() + (src.y() + 1)* FIELD_SIZE] != empty )
                return false;
            else
            {
		saveThere[ pointToIndex(src) ] = true;
                src.ry() += 1;
            }
            break;
        case west:
            if( src.x() - 1 < 0 )
                return false;
            if( m_field[src.x() - 1 + src.y()* FIELD_SIZE] != empty )
                return false;
            else
            {
		saveThere[ pointToIndex(src) ] = true;
                src.rx() -= 1;
            }
            break;
        default:
            return false;
    }
    return true;
}

void KornersEngine::markReachable( QPoint src, direction dir, bool* saveThere, bool jump ) const
{
    if( saveThere[ pointToIndex(src) ] == true )
        return;

    if( ( src.x() >= FIELD_SIZE ) ||
        ( src.x() < 0 )           ||
        ( src.y() >= FIELD_SIZE)  ||
        ( src.y() < 0 ) )
            return;

    if( dir != none )
    {
        if( !jump )
        {
	    if( m_field[ pointToIndex(src) ] == empty )
            {
		saveThere[ pointToIndex(src) ] = true;
                return;
            }
            else
            {
                jump = true;
                if( !tryJump( src, dir, saveThere ) )
                    return;
            }
        }
        else
        {
	    if( m_field[ pointToIndex(src) ] == empty )
                return;
            else
            {
                if( !tryJump( src, dir, saveThere ) )
                    return;
            }
        }
    }

    saveThere[ pointToIndex(src) ] = true;

    // Try to move forward
    for( int i = 1; i < 5; i++ )
    {
        if( ((dir - i == 2) || (dir - i == -2)) && (dir != none) )
            continue;

        if(i == north)
        {
            markReachable( QPoint(src.x(), src.y() - 1), north, saveThere, jump );
        }
        else if(i == east)
        {
            markReachable( QPoint(src.x() + 1, src.y()), east, saveThere, jump );
        }
        else if(i == south)
        {
            markReachable( QPoint(src.x(), src.y() + 1), south,  saveThere, jump );
        }
        else if(i == west)
        {
            markReachable( QPoint(src.x() - 1, src.y()), west, saveThere, jump );
        }
    }
}

void KornersEngine::getAvailableMoves( QPoint from_where )
{
    static QVector<QPoint> returnPoints;
    returnPoints.clear();
    bool reachable[FIELD_SIZE*FIELD_SIZE];
    memset( reachable, false, FIELD_SIZE*FIELD_SIZE );

    markReachable( from_where, none, reachable );
    for(int i  = 0; i < FIELD_SIZE*FIELD_SIZE; i++)
    {
        if( reachable[i] )
            returnPoints.push_back( indexToPoint(i) );
    }
    emit( availableMoves( &returnPoints ) );
}

void KornersEngine::playersMove( QPoint src, QPoint dst )
{
    if( !canMove( src, dst ) )
    {   
        kDebug() << "illegal move";
        emit( canPlay() );
        return;
    }

    KornersMove newMove;
    if( makePath(src, dst, newMove) )
    {
        applyMove( src, dst );
        emit( move(newMove) );
        if( gameOver() == player )
        {
            kDebug() << "You win";
            emit( youWin() );
        }
        makeNextMove(src, dst);
    }
    else
	emit( canPlay() );
}

void KornersEngine::computerMove(QPoint src, QPoint dst)
{
    if( !isMoveValid( src, dst, opponent ) )
    {
        kDebug() << "illegal move";
        emit( engineMessage("Opponent's move not valid !!! He is cheating !! ") );
        return;
    }

    KornersMove newMove;
    if( makePath(src, dst, newMove) )
    {
        applyMove( src, dst );
        emit( move(newMove) );
        if( gameOver() == opponent )
        {
            kDebug() << "You lost";
            emit( youLost() );
            return;
        }
        emit( canPlay() );
    }
    else
        emit( engineMessage("Opponent's move not valid !!! He is cheating !! ") );
}

void KornersEngine::capSelected( QPoint cap )
{
    if( canSelect(cap) )
	getAvailableMoves(cap);
    else
	kDebug() << "Can't select this";
}

void KornersEngine::stop()
{}
